#include "path.h"
#include <QRandomGenerator>
#include <QDebug>
#include <QtGlobal>

Map* Path::map = nullptr;
float Population::cProb = 0.0;
float Population::mProb = 0.0;
float Population::rRate = 0.0;

Path::Path()
{

}

Path::Path(const QList<int> &list):QList<int>(list)
{
}

Path Path::generate()
{
    Path p;
    if(map==nullptr) return p;

    int n = map->count();
    for (int i = 0; i < n; ++i) {
        p.append(i);
    }
    // 随机打乱
    std::shuffle(p.begin(),p.end(),*QRandomGenerator::global());
    p.evaluate();

    return p;
}

void Path::evaluate()
{
    // 计算总代价
    int n = count();
    float dis = 0;
    for(int i=0;i<n-1;i++){
        City* c1 = map->cityList.at(at(i));
        City* c2 = map->cityList.at(at(i+1));
        dis += *c1-*c2;
    }
    dis += *(map->cityList.at(first())) - *(map->cityList.at(last()));
    cost = dis;

    // 适应度函数
    fitness = fitnessFunction(cost);
}

float Path::fitnessFunction(float cost)
{
    return 1/cost;
}

void Path::crossover(Path &p1, Path &p2, int index,float prob)
{
    // 概率小于随机数，不交叉
    if(QRandomGenerator::global()->generateDouble()>prob) return;

    Path result1,result2;
    // 以index为分离点互换
    result1 = p1.first(index);
    result1.append(p2.last(map->count()-index));
    result2 = p2.first(index);
    result2.append(p1.last(map->count()-index));

    // 随机交换重复点
    QList<int> repeat1,repeat2,rid1,rid2;
    for (int i = 0; i < index; ++i) {
        int node = result1.at(i);
        int times = result1.count(node);
        if(times>1) {repeat1.append(node);rid1.append(i);}
        node = result2.at(i);
        times = result2.count(node);
        if(times>1) {repeat2.append(node);rid2.append(i);}
    }
    std::shuffle(repeat1.begin(),repeat1.end(),*QRandomGenerator::global());
    std::shuffle(repeat2.begin(),repeat2.end(),*QRandomGenerator::global());
    for(int i=0;i<rid1.count();i++){
        result1[rid1.at(i)] = repeat2.first();
        repeat2.pop_front();
        result2[rid2.at(i)] = repeat1.first();
        repeat1.pop_front();
    }

    p1 = result1;
    p2 = result2;
    p1.evaluate();
    p2.evaluate();
}

void Path::mutate(float prob)
{
    // 概率小于随机数，不变异
    if(QRandomGenerator::global()->generateDouble()>prob) return;
    // 随机选择两个位置
    int node1 = QRandomGenerator::global()->bounded(0,count());
    int node2 = QRandomGenerator::global()->bounded(0,count());
    // 交换
    int temp = at(node1);
    operator[](node1)=at(node2);
    operator[](node2)=temp;
    evaluate();
}

bool operator>(const Path& p1,const Path& p2){
    return p1.fitness>p2.fitness;
}
bool operator<(const Path& p1,const Path& p2){
    return p1.fitness<p2.fitness;
}

Population::Population()
{

}

Population::Population(const QList<Path> &list):QList<Path>(list)
{
}

Population Population::generate(int n)
{
    Population pop;
    while (pop.count()<n) {
        Path  p = Path::generate();
        if(!pop.contains(p)) // 检查重复路径
            pop.append(p);
    }
    return pop;
}

void Population::sort()
{
    std::sort(begin(),end(),std::greater());
}

Population Population::selectBest(float rate)
{
    Population bestPop;
    this->sort();   // 排序
    bestPop = this->first(qCeil(rate*count())); // 取适应度最高的rate*count个个体
    return bestPop;
}

Population Population::select(int num)
{
    Population selectedPop;
    int n = count();
    float* prob = new float[n];
    float* cp = new float[n];
    float sum = 0;
    // 计算总适应度
    for (int i = 0; i < n; ++i) {
        sum+=at(i).fitness;
    }
    // 计算概率和累计概率
    for (int i = 0; i < n; ++i) {
        prob[i]=at(i).fitness/sum;
        cp[i]=(i==0?prob[i]:(cp[i-1]+prob[i]));
    }
    while(selectedPop.count()!=num) {
        float rand = QRandomGenerator::global()->generateDouble();
        int index = 0;
        for (index=0; index < n; ++index) {
            if(rand<cp[index]){
                if(!selectedPop.contains(at(index))) break;
            }
        }
        if(index==n) selectedPop.append(at(QRandomGenerator::global()->bounded(0,n)));
        else selectedPop.append(at(index));
    }
    delete[] prob;
    delete[] cp;
    return selectedPop;
}

void Population::crossover(float prob)
{
    Population result;
    for (int i = 0; 2*i < count()-1; ++i) {
        Path::crossover(operator[](2*i),operator[](2*i+1),QRandomGenerator::global()->bounded(2,Path::map->count()-1),prob);
    }
}

Population Population::propagate()
{
    Population best = selectBest(rRate);    // 精英保留
    Population parent = select(count()-best.count());   // 选择
    parent.crossover(cProb);    // 交叉
    for (int i = 0; i < parent.count(); ++i) {  // 变异
        if(count(parent.at(i))>1) parent[i].mutate(1);
        else
            parent[i].mutate(mProb);
    }
    best.append(parent);
    best.sort();    // 排序
    return best;
}

QDebug operator<<(QDebug debug,const Population &pop){
    debug<<"个体数目:"<<pop.count()<<Qt::endl;
    foreach (Path p, pop) {
        debug<<"cost:"<<p.cost<<" "<<"fitness:"<<p.fitness<<" "<<p<<Qt::endl;
    }
    return debug;
}
